package 二分.二分答案;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/11 22:33
 */
public class 腾讯笔试 {


    /*
     牛牛有一个长度为n的数组a={a1, a2,..., an}，定义f(a)为数组α中每个元素出现次数的最大值,如:f({1,2,3,3})=2,f({1,1,1})=3.
     现在牛牛最多可以删除k个数字,现在他想使删除若干数字之后的f(a)尽可能的小,删除ai的代价是i,
     请你帮牛牛计算f(a)的最小值以及使f(a)达到最小值的最小代价。

     这个题 的亮点： 不仅求最小值 ，还需要求 最小值的代价


     这个题： 真的不错！， 二分 答案 + 思维题
      1 <k < n < 10 ^ 5
     */

    // 我的思路, 和牛逼， 点个赞
    public void solution(int nums[],int k){
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            List<Integer> orDefault = map.getOrDefault(nums[i], new ArrayList<>());
            orDefault.add(i); // 按照 下标 进行收集， 便于后续 求答案
            map.put(nums[i],orDefault);
        }
        Map.Entry<Integer,List<Integer>>[] entries = map.entrySet().toArray(new Map.Entry[0]);
        // 这个 排序 很抽象
        Arrays.sort(entries,(a,b)-> b.getValue().size() - a.getValue().size());


        int l = 0, r = nums.length;
        while(l < r){
            int mid = l + r >> 1;
            if(check(entries,mid) <= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        System.out.println(l);
        int cost = 0;
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            int count  = entry.getValue().size() - l;
            if(count <= 0){
                break;
            }
            for (int i = 0; i < count; i++) {
                cost += entry.getValue().get(i) + 1;
            }
        }
        System.out.println(cost);
    }

    private int check(Map.Entry<Integer, List<Integer>>[] entries, int mid) {
        int ans = 0;
        for (Map.Entry<Integer, List<Integer>> entry : entries) {
            if(entry.getValue().size() <= mid){
                break;
            }
            ans += entry.getValue().size() - mid;
        }
        return ans;
    }


    @Test
    public void test(){
//        int nums[] = {1,1,1,2,2};
//        int k = 2;
        int k = 3;
        int nums[] = {1,1,1};
        solution(nums,k);
    }


}
